// 四数之和
// [1,0,-1,0,-2,2]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  let result = []
  let len = nums.length
  nums.sort((a, b) => a - b)
  console.log(nums);
  for (let k = 0; k < len - 3; k++) {
    if (nums[k] > target && nums[k] >= 0) break
    if (k > 0 && nums[k] === nums[k - 1]) continue
    for (let i = k + 1; i < len - 2; i++) {
      if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) break
      if (i > k + 1 && nums[i] === nums[i - 1]) continue
      let left = i + 1, right = len - 1
      while (left < right) {
        let sum = nums[k] + nums[i] + nums[left] + nums[right]
        if (sum === target) {
          result.push([nums[k], nums[i], nums[left], nums[right]])

          while (left < right && nums[left] === nums[left + 1]) left++
          while (left < right && nums[right] === nums[right - 1]) right--

          left++
          right--
        } else if (sum < target) {
          left++
        } else {
          right--
        }
      }
    }
  }

  return result
};

console.log(fourSum([1, 0, -1, 0, -2, 2], 0));
